# 421 数组中两个数的最大异或值(好题)
# https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/
# Date: 2025/2/20
from leetcode import test_function as tf


def findMaximumXOR_bf(nums: list[int]) -> int:
    """暴力解法, 超时"""
    n = len(nums)
    res = 0
    for i in range(n):
        for j in range(i, n):
            res = max(nums[i] ^ nums[j], res)
    return res


def findMaximumXOR_hash(nums: list[int]) -> int:
    """
    哈希表
    从最高位到最低位逐位比对, 逐位确定最高位的策略.
    例如:     第1位   第2位    第3位     第4位      第5位
    00011     0|     00|     000|     0001|     00011
    01010     0|     01|     010|     0101|     01010
    00101 --> 0| --> 00| --> 001| --> 0010| --> 00101
    11001     1|     11|     110|     1100|     11001
    00010     0|     00|     000|     0001|     00010
    01000     0|     01|     010|     0100|     01000
    max       1      11      111      1110      11100
    """
    ans = mask = 0
    high_bit = max(nums).bit_length() - 1
    for i in range(high_bit, -1, -1):  # 从最高位开始枚举
        mask |= 1 << i
        new_ans = ans | (1 << i)  # 尝试将当前位设为1作为候选答案
        seen = set()
        for x in nums:  # 遍历集合中的所有数字
            x &= mask  # 仅保留掩码对应的位
            if new_ans ^ x in seen:  # 检查当前是否有异或为1的, 即该位是否可以为1, 若 A ^ B = new_ans 那么 A = B ^ new_ans
                ans = new_ans  # 如果存在，则当前位可以保留为1
                break
            seen.add(x)
    return ans


def findMaximumXOR_trie(nums: list[int]) -> int:
    """通过01字典树来实现"""

    class TrieNode:
        """
        定义字典树的节点
        """

        def __init__(self):
            # 左子树指向表示 0 的子节点
            self.left = None
            # 右子树指向表示 1 的子节点
            self.right = None

    # 字典树的根节点
    root = TrieNode()
    # 最高位的二进制位编号为 30
    high_bit = max(nums).bit_length() - 1

    def add(num: int):
        """添加节点"""
        cur = root
        for k in range(high_bit, -1, -1):
            bit = (num >> k) & 1
            if bit == 0:
                if not cur.left:
                    cur.left = TrieNode()
                cur = cur.left
            else:
                if not cur.right:
                    cur.right = TrieNode()
                cur = cur.right

    def check(num: int) -> int:
        cur = root
        x = 0
        for k in range(high_bit, -1, -1):
            bit = (num >> k) & 1
            if bit == 0:
                # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                if cur.right:
                    cur = cur.right
                    x = x * 2 + 1
                else:
                    cur = cur.left
                    x = x * 2
            else:
                # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                if cur.left:
                    cur = cur.left
                    x = x * 2 + 1
                else:
                    cur = cur.right
                    x = x * 2
        return x

    n = len(nums)
    x = 0
    for i in range(1, n):
        # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
        add(nums[i - 1])
        # 将 nums[i] 看作 ai，找出最大的 x 更新答案
        x = max(x, check(nums[i]))

    return x


if __name__ == '__main__':
    inp = [{"nums": [3, 10, 5, 25, 2, 8]},
           {"nums": [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]},
           ]
    out = [28, 127]

    tf(findMaximumXOR_bf, inp, out)
    tf(findMaximumXOR_hash, inp, out)
    tf(findMaximumXOR_trie, inp, out)
